The following disclosure generally relates to navigation, and, more particularly, to compiling a navigation database for providing an optimal route.
Navigation systems may be provided on various different computer platforms. For example, a navigation system may be a standalone system or a networked system. In a standalone navigation system, the software applications, geographic data, and hardware are combined at a single location. The standalone system may be installed in a vehicle or carried by a person. In a networked navigation system, some of the software or geographic data is/are located with the hardware with the user and some of the software or geographic data is/are located remotely and accessed over a communications system. The navigation system may be implemented on a dedicated platform in which the hardware and software are specifically designed for navigation purposes. Alternatively, the navigation system may be implemented on a general purpose computing platform (e.g., a personal computer, personal digital assistant, smart phone, or a networked computer) using appropriate navigation-related software applications and data.
Navigation systems provide a variety of useful features and services. For example, navigation systems used in vehicles can provide detailed instructions for driving to desired destinations, thereby reducing travel times and expenses. Navigation systems and navigation applications can also search for businesses of a desired type and provide routing guidance to locations of such businesses.
Finding an acceptable route from a starting point S to a destination point D is the core functionality of a navigation system. Most navigation systems do not attempt to determine an “optimum” route from S to D, as such a determination, which would require analyzing all of the links in the navigation system, would be both memory and time-intensive. For example, computing the “optimum” route from a starting point S in Madrid to a destination point D in Moscow may take upwards of an hour on an embedded navigation system.
Instead, most navigation systems aim to determine and provide an acceptable route, in a timely manner, for a given cost function (e.g., “the shortest route,” “the fastest route,” etc.). These navigation systems may, for example, utilize a navigation database created according to the Navigation Data Standard (“NDS”). NDS databases include a 5-layer or level hierarchical graph structure. Each layer or level of the graph structure may be divided into tiles, or equally-sized areas, and includes only those links or road segments that belong to a specific functional road class (“FRC”). Each link may, for example, be assigned a FRC value between 1 and 5, with the assigned value reflecting the importance of the link for route calculations (e.g., a FRC value of 1 indicates that the link is the most important for route calculation purposes). The links are then placed into one of the layers or levels based on the assigned FRC value. When these navigation systems are attempting to find an acceptable route between a starting point and a destination point, these navigation systems may “explore” all links on a routing level (e.g., the lowest routing level) around the starting point and the destination point. The system may then apply heuristics to determine when to switch from the lowest routing level to another level (e.g., the second lowest routing level). Using this approach, the navigation system may calculate, in a timely manner, the appropriate, but not necessarily optimal, route from the starting point and the destination point.